package com.xc.arr;

class BinarySearchTree {
    private TreeNode root;

    BinarySearchTree() {
        root = null;
    }

    // 插入节点
    void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) {//第一个节点为null
            return new TreeNode(val);
        }

        if (val < node.val) {//val（30）比50（根节点），查到节点左边
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }

        // 更新节点的高度
        int height = getHeight(node);
        if (height > 1 && val < node.left.val) {
            // 左子树的左子树高度大于1，需要旋转
            node.left = rotateLeft(node.left);
            node = rotateRight(node);
        } else if (height > 1 && val > node.right.val) {
            // 右子树的右子树高度大于1，需要旋转
            node.right = rotateRight(node.right);
            node = rotateLeft(node);
        }

        return node;
    }

    // 左旋
    private TreeNode rotateLeft(TreeNode node) {
        TreeNode temp = node.right;
        node.right = temp.left;
        temp.left = node;
        node = temp;
        return node;
    }

    // 右旋
    private TreeNode rotateRight(TreeNode node) {
        TreeNode temp = node.left;
        node.left = temp.right;
        temp.right = node;
        node = temp;
        return node;
    }

    // 获取节点的高度
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 中序遍历
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    private void inorderTraversal(TreeNode node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.print(node.val + " ");
            inorderTraversal(node.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);
        System.out.println("Inorder traversal: ");
        bst.inorderTraversal();
    }
}

class TreeNode {
    int val;
    int height;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.height = 1;
    }
}